import java.util.Arrays;
import java.util.HashMap;

public class LeetCode167 {
    public static void main(String[] args) {
        int[] ints = twoSum(new int[]{2, 7, 11, 15}, 13);
        System.out.println(Arrays.toString(ints));
    }

    public static int[] twoSum(int[] numbers, int target) {
        /**
         * 左右指针走，然后用一个map来存走过的数字，每次都判断当前下标的数字对于的数字在map中是否有
         * key为数字，value为下标
         */
        int l =0,r = numbers.length -1;
        int[] re = new int[2];
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        while (l <= r){
            if (hashMap.get(target - numbers[l]) != null){
                Integer value = hashMap.get(target - numbers[l]);
                if (value  > l){
                    re[0] = l + 1;
                    re[1] = value + 1;
                }else {
                    re[1] = l + 1;
                    re[0] = value + 1;
                }

                return re;
            }
            hashMap.put(numbers[l],l);

            if (hashMap.get(target - numbers[r]) != null){
                Integer value = hashMap.get(target - numbers[r]);
                if (value  > r){
                    re[0] = r + 1;
                    re[1] = value + 1;
                }else {
                    re[1] = r + 1;
                    re[0] = value + 1;
                }

                return re;
            }
            hashMap.put(numbers[r],r);

            l++;
            r--;
        }
    return  re;
    }


    /**
     * 由于是有序的则如果左右指针和大于目标值则右指针移动否则左指针移动
     * @param numbers
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] numbers, int target){
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[]{-1, -1};
    }
}
